"""
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
"""
class Solution(object):
    #* 类似于 MaxProfitIII，建立长度 2k 的动态规划数组
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k == 0: return 0
        n = len(prices)
        if n <= 1: return 0

        dp = [0] * (2*k)  # vertical array
        for j in range(k):
            dp[2*j] = -prices[0]
        
        for i in range(1, n):
            dp[0] = max(dp[0], -prices[i])
            dp[1] = max(dp[1], dp[0]+prices[i])
            for j in range(1, k):
                dp[2*j] = max(dp[2*j], dp[2*j-1]-prices[i])
                dp[2*j+1] = max(dp[2*j+1], dp[2*j]+prices[i])
        
        return dp[-1]
